package swardToOffer.method_2_sort_or_find.find;

/**
 * @Author ChanZany
 * @Date 2021/5/26 15:05
 * @Version 1.0
 * 面试题56（二）：数组中唯一只出现一次的数字
 * 题目：在一个数组中除了一个数字只出现一次之外，其他数字都出现了三次。请
 * 找出那个只出现一次的数字。
 * 思路:如果将数组中所有数字的二进制表示的每一位都加起点,如果某一位的和能被3整除,则那个
 * 只出现一次的数字二进制表示中对应的那一位是0;
 */
public class NumberAppearingOnce {
    public int singleNumber(int[] nums) {
        int[] bitSum = new int[32];
        for (int num : nums) {
            int m = 1;
            for (int i = 31; i >= 0; i--) {
                bitSum[i] += (num & m) != 0 ? 1 : 0;
                m <<= 1;
            }
        }
        int res = 0;
        for (int i = 0; i < 32; i++) {
            res = res<<1; //1->10 11->110
            res |= bitSum[i] % 3; //10 | 01 -> 11 110|001->111
        }
        return res;
    }
    public int singleNumber2(int[] nums) {
        int ones = 0, twos = 0;
        for(int num : nums){
            ones = ones ^ num & ~twos;
            twos = twos ^ num & ~ones;
        }
        return ones;
    }
    public static void main(String[] args) {
        NumberAppearingOnce Main = new NumberAppearingOnce();
        int [] nums = new int[]{1,6,1,1};
        System.out.println(Main.singleNumber2(nums));
    }
}
